/**
 * Created With IntelliJ IDEA
 * Description:牛客网:BM47 寻找第K大
 * <a href="https://www.nowcoder.com/practice/e016ad9b7f0b45048c58a9f27ba618bf?tpId=295&tqId=44581&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj">...</a>
 * User: DELL
 * Data: 2023-03-10
 * Time: 23:18
 */

//利用快排的思路,但是不需要将全部均排序好,即每次递归均只递归下标包含K的那一部分即可
public class Solution {
    public int findKth(int[] a, int n, int K) {
        adjust(a,0,n-1,n-K);
        return a[n-K];
    }
    private void adjust (int[] a, int left, int right, int K) {
        if (left >= right) {
            return;
        }
        int base = a[left];
        int i = left;
        int j = right;
        while (i < j) {
            while (i < j && a[j] >= base) {
                j--;
            }
            while (i < j && a[i] < base) {
                i++;
            }
            if (i < j) {
                int tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
            }
        }
        if (i >= K) {
            adjust(a,left,i,K);
        } else {
            adjust(a,i+1,right,K);
        }
    }
}